emmm...是的,又是最短路.
前置知识点:
1.邻接表2.SPFA
例题:P5960 【模板】差分约束
差分约束系统:一个由n个变量和m个约束条件(不等式)组成.
其实就是求解一组变量的不等式组的算法.
题意很清楚,这里就不进行分析了.
思路:
(这题的写法还是蛮多的,此处介绍一种)
此题一眼看不出来是最短路.这是难点.
就算知道是最短路后,也不知道也么写.这更是难点.
这里,作者将分析如何使用最短路解决此题.
方案:将不等式转换.
以样例为例:
这个 xc1−xc2≤3x_{c1}-x_{c2}\le 3xc1 −xc2 ≤3
可以转换为这个 xc1≤xc2+3x_{c1} \le x_{c2}+3xc1 ≤xc2 +3
似乎令人眼熟 ,不是吗?
dis[i]≤dis[j]+lendis[i]\le dis[j]+lendis[i]≤dis[j]+len (松弛)
所以,我们可以将333是做lenlenlen,而这里的len就是点jjj和点iii之间的一条路径(单向)
那么整个样例就可以转换成:
而且,同样地,xc1x_{c_1}xc1 就可以转换成dis[1]dis[1]dis[1].
但是也会诞生一个问题,在最短路中,dis[x]dis[x]dis[x]表示的是起点到点xxx的距离.
那么此时的起点是谁? 答:是超级原点.
它长这样:
此时的"0"就是那个超级原点.
超级原点和图中的每一个点都有一条长度为0的边.
因为没有明确的"起点",所以才会有超级原点.
添加一个超级原点,其实就是将某一个点(0/n+1)与其他所有的点增加一条长度为0的边.
代码如下:
但是,可能会有人问:
如果说所有dis[x]dis[x]dis[x]都是0的话,输出的不是也全都是0吗?
这是因为,不等式中,会有负数的存在.
所以说,在这种方法下求解出的不等式组,它的每一个变量,都是≤0\le0≤0的.
最后还有一个问题:无解.
其实,这里的无解也很好理解,就是所谓的:负环.
在做SPFA的时候,判断一下负环就可以判断不等式是否无解了.
代码:
应用范围:
差分约束主要用于一些有"至少","至多"字眼的题目